백준 1766번

문제집

Posted by ChoiCube84 on February 01, 2024 · 9 mins read
프로그래밍 문제풀이

백준 1766번

오늘 풀어본 문제는 백준의 1766번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

민오는 $1$ 번부터 $N$ 번까지 총 $N$ 개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 $1$ 번 문제가 가장 쉬운 문제이고 $N$ 번 문제가 가장 어려운 문제가 된다.

어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 ‘먼저 푸는 것이 좋은 문제’가 있다는 것을 알게 되었다. 예를 들어 $1$ 번 문제를 풀고 나면 $4$ 번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.

  1. $N$ 개의 문제는 모두 풀어야 한다.

  2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.

  3. 가능하면 쉬운 문제부터 풀어야 한다.

예를 들어서 네 개의 문제가 있다고 하자. $4$ 번 문제는 $2$ 번 문제보다 먼저 푸는 것이 좋고, $3$ 번 문제는 $1$ 번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 $4-3-2-1$ 의 순서로 문제를 풀게 되면 조건 $1$ 과 조건 $2$ 를 만족한다. 하지만 조건 $3$ 을 만족하지 않는다. $4$ 보다 $3$ 을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 $3$ 을 만족하는 문제를 풀 순서는 $3-1-4-2$ 가 된다.

문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.

입력

첫째 줄에 문제의 수 $N$ $(1 \le N \le 32,000)$ 과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 $M$ $(1 \le M \le 100,000)$ 이 주어진다. 둘째 줄부터 $M$ 개의 줄에 걸쳐 두 정수의 순서쌍 $A,B$ 가 빈칸을 사이에 두고 주어진다. 이는 $A$ 번 문제는 $B$ 번 문제보다 먼저 푸는 것이 좋다는 의미이다.

항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 문제 번호를 나타내는 $1$ 이상 $N$ 이하의 정수들을 민오가 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.

풀이과정

1번째 시도

문제를 보고 위상정렬을 이용해야 하는 문제라는 것을 알 수 있었다. 그러나 다른 문제들과는 달리 위상정렬 상에서는 순서가 상관없는 수 끼리라도 더 작은 수가 최대한 먼저와야 한다는 것을 알 수 있었다.

내가 가장 먼저 생각한 방법은 $1$ 부터 $N$ 까지 차례로 이동하면서 entryDeg 가 $0$ 인 경우는 즉시 출력하고, 연결된 다른 노드들의 entryDeg 를 감소시켜준 후, 감소되었다면 마찬가지로 출력시켜주는 방법을 생각하였다. 이 과정에서 출력해야할 노드가 여러 개일 수 있으므로, priority_queue 를 이용하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N+1);
    vector<int> entryDeg(N+1, 0);

    for (int i=0; i<M; i++) {
        int former, latter;
        cin >> former >> latter;

        graph[former].emplace_back(latter);
        entryDeg[latter]++;
    }

    for (int i=1; i<=N; i++) {
        if (entryDeg[i] == 0) {
            cout << i << " ";

            priority_queue<int> pq;

            for (auto& next : graph[i]) {
                entryDeg[next]--;

                if (entryDeg[next] == 0 && next < i) {
                    pq.push(next);
                }
            }

            while (!pq.empty()) {
                cout << pq.top() << " ";
                pq.pop();
            }
        }
        else {
            continue;
        }
    }
    
    return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

2번째 시도

문제가 되었던 부분은 몇몇 번호들이 전혀 출력되지 않을 수 있다는 점이었다. 어떤 문제의 먼저 풀어야할 문제도 그보다 먼저 풀어야할 문제가 있다면, entryDeg 를 제 때 줄여주지 않아 문제가 될 수 있는 것이었다.

이를 해결하기 위해 $1$ 에서 $N$ 까지 차례로 이동하는 대신 priority_queue 를 바깥으로 빼주어 깊이 숨어있는 수들도 탐색할 수 있도록 해주었다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N+1);
    vector<int> entryDeg(N+1, 0);

    for (int i=0; i<M; i++) {
        int former, latter;
        cin >> former >> latter;

        graph[former].emplace_back(latter);
        entryDeg[latter]++;
    }

    priority_queue<int, vector<int>, greater<>> pq;

    for (int i=1; i<=N; i++) {
        if (entryDeg[i] == 0) {
            pq.push(i);
        }
    }

    while (!pq.empty()) {
        int curr = pq.top();
        pq.pop();

        if (entryDeg[curr] == 0) {
            cout << curr << " ";

            for (auto& next : graph[curr]) {
                entryDeg[next]--;

                if (entryDeg[next] == 0) {
                    pq.push(next);
                }
            }
        }
    }

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

위상정렬에 우선순위 큐를 섞어서 추가적인 제약을 구현할 수 있다는 점이 흥미로운 문제였다. 위상정렬 문제는 자신있는 분야라고 생각했는데, 이번에 또 한 수 배우게 된 것 같다.

이제 CLASS 5 를 모두 풀기까지 $9$ 문제 만이 남아있다. 지금의 추세라면 군대가기 전까지 다 끝낼 수 있을 것 같다. 마저 힘내서 풀어야겠다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/1766

← Previous Post Next Post →